package 开始的剑指offer8月.查找算法;
// https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
public class 剑指Offer03数组中重复的数字0816 {
    //哈希
    // class Solution {
//     public int findRepeatNumber(int[] nums) {
//         Set<Integer> set = new HashSet<Integer>();
//         int repeat = -1;
//         for (int num : nums) {
//             if (!set.add(num)) {
//                 repeat = num;
//                 break;
//             }
//         }
//         return repeat;

    //     }
// }
    //双指针
    class Solution {//原地置换
        public int findRepeatNumber(int[] nums) {
            if (nums.length == 0) {
                return -1;
            }
            for (int i = 0; i < nums.length; ++i) {
                while (nums[i] != i) {
                    //发现重复元素
                    if (nums[i] == nums[nums[i]]) {
                        return nums[i];
                    }
                    //置换，将指针下的元素换到属于他的索引处
                    int temp = nums[i];
                    nums[i] = nums[temp];
                    nums[temp] = temp;
                }
            }
            return -1;
        }
    }
}
